package src.BlueBridge.DeepRecursion;

import java.util.HashSet;
import java.util.Set;

/**
 * 实现一种算法，打印n对括号的全部有效组合(即左右括号正确配对)
 * 示例，输入:3
 * 输出:((())), (()()), (())(), ()(()), ()()()
 *
 * S(n) = 对S(n - 1)中的每一个元素进行添左，添右，添外
 */

public class _4合法括号 {
    public static void main(String[] args) {
        System.out.println(parenthesis(3));
        System.out.println(mySolve2(3));
    }

    // 逐步生成之迭代解法
    public static Set<String> parenthesis1(int n) {
        Set<String> set = new HashSet<>();
        set.add("()");
        if (n == 1) {
            return set;
        }
        for (int i = 2 ; i <= n ; i++) {
            Set<String> newSet = new HashSet<>();
            for (String ele : set) {
                newSet.add(ele + "()");
                newSet.add("()" + ele);
                newSet.add("(" + ele + ")");
            }
            set = newSet;
        }
        return set;
    }

    // 逐步生成之递归解法
    // 整块代码分为两个部分
    public static Set<String> parenthesis(int n) {
        // 先定义出每一层递归的set
        Set<String> s_n = new HashSet<>();
        // 当探底探到n为1时，初始化字符串并加入当前层的set
        if (n == 1) {
            s_n.add("()");
            return s_n;
        }
        // 一直探底，直到n为1
        Set<String> s_n_1 = parenthesis(n - 1);

        // 从上层递归出来，返回的是上一层的set，再给上一层的set的每个
        // 字符串加入括号，放入当前层的set中
        for (String eOfN : s_n_1) {
            s_n.add("()" + eOfN);
            s_n.add(eOfN + "()");
            s_n.add("(" + eOfN + ")");
        }
        // 最后返回最上层的set
        return s_n;
    }

    // 迭代
    public static Set<String> mySolve1(int n) {
        Set<String> set = new HashSet<>();
        set.add("()");
        if (n == 1) {
            return set;
        }
        for (int i = 2 ; i <= n ; i++) {
            HashSet<String> newSet = new HashSet<>();
            for (String item : set) {
                newSet.add(item + "()");
                newSet.add("(" + item + ")");
                newSet.add("()" + item);
            }
            set = newSet;
        }
        return set;
    }

    // 递归
    public static Set<String> mySolve2(int n) {
        Set<String> s_n = new HashSet<>();
        if (n == 1) {
            s_n.add("()");
            return s_n;
        }
        Set<String> s_n_1 = mySolve2(n - 1);
        for (String ele : s_n_1) {
            s_n.add("()" + ele);
            s_n.add("(" + ele + ")");
            s_n.add(ele + "()");
        }
        return s_n;
    }
}
